#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e6+100;
typedef int LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
char str[maxn];
LL sum[maxn];
LL dp[maxn][2];
int main(void){
   cin.tie(0);std::ios::sync_with_stdio(false);
   LL t;cin>>t;
   while(t--){
      LL n,k;cin>>n>>k;
      for(LL i=1;i<=n;i++) cin>>str[i];
      sum[0]=dp[0][0]=dp[0][1]=0;
      for(LL i=1;i<=n;i++){
         sum[i]=sum[i-1]+(str[i]-'0');
      }
      dp[1][1]=(str[1]=='0');
      dp[1][0]=(str[1]=='1');
      for(LL i=1;i<=n;i++){
         dp[i][0]=min(dp[i-1][0],dp[i-1][1])+(str[i]=='1');
         if(i>=k){
             dp[i][1]=min(sum[i-1],dp[i-k][1]+sum[i-1]-sum[i-k])+(str[i]=='0');
         }
         else dp[i][1] = min(sum[i-1],dp[0][1]+sum[i - 1]-sum[0])+(str[i]=='0');
      }
      cout<<min(dp[n][1],dp[n][0])<<"\n";
   }
   return 0;
}
